/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-03 15:40:54
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-03 20:02:52
 * @FilePath: \LeetCode\239.滑动窗口最大值.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=239 lang=cpp
 *
 * [239] 滑动窗口最大值
 *
 * 方法1：构建大小为 k 的最大堆  first：数值 second：下标
 * - 滑动窗口：当堆顶元素不在窗口时 pop()
 * - 问题：最大堆元素频繁更新影响性能
 *
 * 官方题解2：单调队列  使用一个队列存储所有还没有被移除的下标
 * - 在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组 nums 中对应的值是严格单调递减的
 * - 为了保持队列的性质，我们会不断地将新的元素与队尾的元素相比较，如果前者大于等于后者，那么队尾的元素就可以被永久地移除，我们将其弹出队列
 * - 队首下标对应的元素就是滑动窗口中的最大值
 */

#include <vector>
#include <queue>
#include <deque>
#include <iostream>

// @lc code=start
class Solution
{
public:
    std::vector<int> maxSlidingWindow_01(std::vector<int> &nums, int k)
    {
        const int len = nums.size();
        std::vector<int> result;

        int i;
        /* 最大堆  first：数值(降序)  second：下标(升序) */
        std::priority_queue<std::pair<int, int>> maxHeap;

        /* 初始化 */
        for (i = 0; i < k; i++)
            maxHeap.push({nums[i], i});
        result.push_back(maxHeap.top().first);

        /* 滑动窗口 */
        for (i = k; i < len; i++)
        {
            maxHeap.push({nums[i], i});
            while (maxHeap.top().second <= i - k)
                maxHeap.pop();
            result.push_back(maxHeap.top().first);
        }

        return result;
    }

    std::vector<int> maxSlidingWindow_02(std::vector<int> &nums, int k)
    {
        const int len = nums.size();
        std::vector<int> result;

        /* 下标递增(队列性质) nums值单调递减(队尾操作) */
        std::deque<int> decreaseQueue;

        /* 初始化 */
        for (int i = 0; i < k; i++)
        {
            while (!decreaseQueue.empty() &&
                   nums[i] >= nums[decreaseQueue.back()])
                decreaseQueue.pop_back(); // 保证队列单调

            decreaseQueue.push_back(i);
        }
        result.push_back(nums[decreaseQueue.front()]);

        /* 滑动窗口 */
        for (int i = k; i < len; i++)
        {
            while (!decreaseQueue.empty() &&
                   nums[i] >= nums[decreaseQueue.back()])
                decreaseQueue.pop_back(); // 保证队列单调

            decreaseQueue.push_back(i);
            /* 淘汰窗口外元素 */
            while (decreaseQueue.front() <= i - k)
                decreaseQueue.pop_front();

            result.push_back(nums[decreaseQueue.front()]);
        }

        return result;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::vector<int> nums = {9, 10, 9, -7, -4, -8, 2, -6};

    // for (auto n : solution.maxSlidingWindow(nums, 5))
    //     std::cout << n << " ";
    // std::cout << std::endl;

    return 0;
}